package algorithm.middle;

import javax.print.attribute.IntegerSyntax;
import java.util.HashMap;

/**
 * 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
 * <p>
 * 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
 * <p>
 * <p>
 * <p>
 * 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
 * <p>
 * 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
 * <p>
 * 请返回待替换子串的最小可能长度。
 * <p>
 * 如果原字符串自身就是一个平衡字符串，则返回 0。
 */
public class BalancedString1234 {
    /**
     * <a href="https://leetcode.cn/problems/replace-the-substring-for-balanced-string/solutions/2108358/tong-xiang-shuang-zhi-zhen-hua-dong-chua-z7tu/">...</a>
     * m = s.length/4 m代表每个字母应该出现几次
     * 如果子串外面的元素，有任意一个字母个数超过m个。这个字串无论如何替换，都无法成功
     * 如果字串外面的元素，每个字母元素个数都不超过m个，说明该字串是可以作为替换的
     * 使用双指针。枚举right指针，移动left，寻找符合条件的最小字串
     */
    public static int balancedString(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        char[] array = s.toCharArray();
        map.put('Q', 0);
        map.put('W', 0);
        map.put('E', 0);
        map.put('R', 0);
        for (char c : array) {
            map.put(c, map.get(c) + 1);
        }
        int m = array.length / 4;
        if (map.get('Q') == m && map.get('W') == m && map.get('E') == m && map.get('R') == m) {
            return 0;
        }
        int left = 0, right = 0;
        int res = array.length;
        for (; right < array.length; right++) {
            //right每往右移动，子串外面的元素就减少一个
            map.put(array[right], map.get(array[right]) - 1);
            while (left <= right && map.get('Q') <= m && map.get('W') <= m && map.get('E') <= m && map.get('R') <= m) {
                res = Math.min(res, right - left + 1);
                map.put(array[left], map.get(array[left]) + 1);
                left++;
            }
        }
        return res;
    }


    public static void main(String[] args) {
        balancedString("QQQW");
    }

}
